class Solution3 {
    public static void main(String[] args) {
         int[] arr= {1, 2, 5} ;
        System.out.println(change(5 , arr ));
    }
    public static int change(int amount, int[] coins) {
           int len = coins.length ;
           int[][] dp = new int[len+1][amount+1] ; 
           dp[0][0] = 1 ;
           for(int i=1 ; i<= len ; i ++){
            for(int j=1 ; j <= amount ; j ++){
               dp[i][j] = dp[i-1][j] ; 
               if(j>=coins[i-1]){
                dp[i][j] += dp[i][j-coins[i-1]];
               }
            }
           }
        return dp[len][amount] ; 
    }
}